package datastruct.hash;


import java.util.TreeMap;

/**
 * @author RunningShrimp
 * @date 2021/5/30  18:14
 * @see <a href=""></a>
 */
public class HashTable<K, V> {
    private TreeMap<K, V>[] hashTable;
    private int M;
    private int size;

    private static final int upperTol = 10;
    private static final int lowerTol = 2;
    private static final int initCapacity = 7;

    public HashTable(int M) {
        this.M = M;
        this.size = 0;
        this.hashTable = new TreeMap[M];
        for (int i = 0; i < M; i++) {
            hashTable[i] = new TreeMap<>();

        }
    }

    public HashTable() {
        this(initCapacity);
    }

    private int hash(K key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }

    public int getSize() {
        return size;
    }

    public void add(K key, V value) {
        TreeMap<K, V> map = hashTable[hash(key)];
        if (map.containsKey(key)) {
            map.put(key, value);
        } else {
            map.put(key, value);
            size++;
        }

        if (size >= upperTol * M) {
            resize(2 * M);
        }
    }

    public V remove(K key) {
        TreeMap<K, V> map = hashTable[hash(key)];

        V ret = null;
        if (map.containsKey(key)) {
            ret = map.remove(key);
            size--;
        }
        return ret;
    }

    public void remove(K key, V value) {
        TreeMap<K, V> map = hashTable[hash(key)];
        if (map.containsKey(key)) {
            map.put(key, value);
            if (size < lowerTol * M && M / 2 >= initCapacity) {

                resize(M / 2);
            }
        } else {
            throw new IllegalStateException(key + "不存在");
        }
    }

    private void resize(int size) {
        TreeMap<K, V>[] newHashes = new TreeMap[size];
        for (int i = 0; i < size; i++) {
            newHashes[i] = new TreeMap<>();
        }
        int old = M;
        this.M = size;
        for (int i = 0; i < old; i++) {
            TreeMap<K, V> map = hashTable[i];
            for (K key : map.keySet()) {
                newHashes[hash(key)].put(key, map.get(key));
            }
        }
        this.hashTable = newHashes;
    }

    public boolean contains(K key) {
        return hashTable[hash(key)].containsKey(key);
    }

    public V get(K key) {
        return hashTable[hash(key)].get(key);
    }
}
